package com.zrf.base.knowledge.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * //给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 * //
 * // 示例:
 * //
 * // 输入: [1,2,3]
 * //输出:
 * //[
 * //  [1,2,3],
 * //  [1,3,2],
 * //  [2,1,3],
 * //  [2,3,1],
 * //  [3,1,2],
 * //  [3,2,1]
 * //]
 * // Related Topics 回溯算法
 * // 👍 957 👎 0
 *
 * @author zhouruifeng
 * @date 2020-10-25 12:08:09
 */
public class Permutations {
    public static void main(String[] args) {
        Solution solution = new Permutations().new Solution();
        System.out.println(solution.permute(new int[]{1, 2, 3}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> resultList = new ArrayList<>();
            List<Integer> resultItem = new ArrayList<>();
            allCom(nums, resultItem, resultList, 0);
            return resultList;
        }

        private void allCom(int[] nums, List<Integer> resultItem, List<List<Integer>> resultList, Integer first) {
            if (resultItem.size() == nums.length) {
                resultList.add(new ArrayList<>(resultItem));
                return;
            }

            for (int i = first; i < nums.length; i++) {
                swap(nums, i, first);
                resultItem.add(nums[first]);

                allCom(nums, resultItem, resultList, first + 1);
                swap(nums, first, i);
                resultItem.remove(resultItem.size() - 1);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}